from cmath import log
from typing import *
from math import inf
from functools import cache


class Solution:
    def findPermutation(self, nums: List[int]) -> List[int]:
        n = len(nums)

        @cache
        def f(limit, pre):
            if limit == 0:
                return abs(pre - nums[0])
            ans = inf
            for i in range(n - 1):
                if limit >> i & 1 == 1:
                    ans = min(ans, f(limit ^ (1 << i), i + 1) + abs(pre - nums[i + 1]))
            return ans

        ans, limit = [0], (1 << (n - 1)) - 1
        for i in range(n - 1):
            aim = f(limit, ans[-1])
            for j in range(n - 1):
                if limit >> j & 1 == 1 and aim == f(limit ^ (1 << j), j + 1) + abs(
                    ans[-1] - nums[j + 1]
                ):
                    ans.append(j + 1)
                    limit ^= 1 << j
                    break
        return ans


s = Solution()
print(s.findPermutation([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]))
print(
    s.findPermutation([6, 7, 8, 0, 5, 3, 2, 9, 4, 1]) == [0, 3, 5, 4, 8, 1, 9, 7, 2, 6]
)
print(s.findPermutation([6, 7, 8, 0, 5, 3, 2, 9, 4, 1]))
print(s.findPermutation([0, 2, 1]))
print(s.findPermutation([1, 0, 2]))
# print(4 >> 1 & 1)
